home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 9066 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.5 KB

  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Special linked list
  5. Date: 7 Mar 1996 16:35:56 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4hnvdcINN165@keats.ugrad.cs.ubc.ca>
  8. References: <4hn7ov$e1t@eng_ser1.erg.cuhk.hk>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4hn7ov$e1t@eng_ser1.erg.cuhk.hk>,
  12. ERiC LEE <cslee@cs.cuhk.hk> wrote:
  13. >    Is there a method to build a linked list using struct & pointer, 
  14. >where the linked list (in fact a two-dimensional linked list, where for 
  15. >example, b3 has 2 pointers at b4 & a3, which is also pointed by b2 & c3) 
  16. >is as shown below? (All the data are long integers)
  17.  
  18. Yes there is. This loosely corresponds to a data structure known as a ``sparse
  19. matrix''.
  20.  
  21. One way is to keep two arrays of pointers; a horizontal vector and a vertical
  22. vector. The horizontal vector contains chains that link elements horizontally.
  23. The vertical vector links---you guessed it---vertically. As in:
  24.  
  25.     x[0]    x[1]    x[2]    x[3]    ...    x[n]
  26.     |    |    |    |        |
  27.     |    v    v    |        v
  28. y[0]----------->z(1,0)->z(2,0)----------------->z(n,0)-->
  29.     |    |    |    |
  30.     v    |    |    v        v
  31. y[1]--->z(0,1)----------------->z(3,1)--------->z(n,1)-->
  32. .    |    |    |    |        |
  33.  
  34. .    .    .    .    .        .
  35. .    |    |    |    |        |
  36. y[m]----z(0,m)--------------------------------->z(n,m)-->
  37.     |    |    |    |        |
  38.     v    v    v    v    ...    v
  39.  
  40.  
  41. The lists are typically doubly-linked. The idea is that using this data
  42. structure you can represent large matrices that are sparsely populated with
  43. elements without reserving storage for the whole matrix.
  44.  
  45.  
  46. -- 
  47.  
  48.